package day19;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/19 11:02
 */

import java.util.*;

/**
 * 给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
 *
 *
 *
 * 示例 1：
 *
 * 输入：words = ["abcd","dcba","lls","s","sssll"]
 * 输出：[[0,1],[1,0],[3,2],[2,4]]
 * 解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
 * 示例 2：
 *
 * 输入：words = ["bat","tab","cat"]
 * 输出：[[0,1],[1,0]]
 * 解释：可拼接成的回文串为 ["battab","tabbat"]
 * 示例 3：
 *
 * 输入：words = ["a",""]
 * 输出：[[0,1],[1,0]]
 */
public class Solution4 {
    List<List<Integer>> ans;
    Map<String, Integer> map;

    public List<List<Integer>> palindromePairs(String[] words) {
        ans = new ArrayList<>();
        map = new HashMap<>();
        int n = words.length;
        for (int i = 0; i < n; i++) map.put(words[i], i);
        for (int i = 0; i < n; i++) {
            // 空串特殊处理
            if (!"".equals(words[i])) f(words[i], i);
        }
        return ans;
    }

    // 判断 s 是否为回文串
    boolean check(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }

    void f(String s, int idx) {
        int n = s.length();
        String rs = new StringBuilder(s).reverse().toString();
        // 存在 s 的翻转字符串，直接添加到右边
        if (map.containsKey(rs) && map.get(rs) != idx) {
            ans.add(Arrays.asList(idx, map.get(rs)));
        }
        // 本身是回文串的，考虑和空串的关系
        if (check(s, 0 , s.length() - 1) && map.containsKey("")) {
            ans.add(Arrays.asList(map.get(""), idx));
            ans.add(Arrays.asList(idx, map.get("")));
        }
        // 添加到左边可以实现回文的
        int r = 1;
        while (r < n) {
            if (check(s, 0, r - 1)) {
                String s1 = rs.substring(0, n - r);
                if (map.containsKey(s1)) ans.add(Arrays.asList(map.get(s1), idx));
            }
            r++;
        }
        // 添加到右边可以实现回文的
        r = 1;
        while (r < n) {
            if (check(rs, 0, r - 1)) {
                String s1 = rs.substring(r, n);
                if (map.containsKey(s1)) ans.add(Arrays.asList(idx, map.get(s1)));
            }
            r++;
        }
    }
}
